import java.util.*;
/**
 * DP41 模版 01背包
 * https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic
 * -programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
 */
public class Exerciser1 {
    static int N = 1010;
    static int n;
    static int V;
    static int[] v = new int[N];
    static int[] w = new int[N];
    static int[][] dp;

    /**
     * 滚动数组进行优化
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        V = in.nextInt();
        for(int i = 1;i <= n;i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        // 第一问
        // dp[i][j]: 从前i个物品中挑选，总体积不超过 j下，所有的选择中，最大的价值
        // 第二问
        // dp[i][j]: 从前i个物品中挑选，总体积正好等于 j下，所有的选择中，最大的价值
        // 保存 j 位置的dp
        int[] dp = new int[V + 1];

        // 第一问
        for(int i = 1;i <= n;i++) {
            for(int j = V;j >= v[i];j--) {
                // 不选择当前的和选择当前位置的值的数据的最大值
                dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[V]);

        for(int i = 0;i <= n;i++) {
            Arrays.fill(dp,0);
        }
        for(int j = 1;j <= V;j++) {
            dp[j] = -1;
        }
        // 第二问
        for(int i = 1;i <= n;i++) {
            for(int j = V;j >= v[i];j--) {
                // 不选择当前的和选择当前位置的值的数据的最大值
                // 但是是存在条件的，当 dp[i][j] == -1 的时候，说明这个位置的体积数不等于j的，是不合法的
                if (dp[j - v[i]] != -1) {
                    dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[V] == -1 ? 0 : dp[V]);
    }

    /**
     * 正常 动态递归
     * @param args
     */
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        V = in.nextInt();
        for(int i = 1;i <= n;i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        // 第一问
        // dp[i][j]: 从前i个物品中挑选，总体积不超过 j下，所有的选择中，最大的价值
        // 第二问
        // dp[i][j]: 从前i个物品中挑选，总体积正好等于 j下，所有的选择中，最大的价值
        dp = new int[n + 1][V + 1];

        // 第一问
        for(int i = 1;i <= n;i++) {
            for(int j = 0; j <= V;j++) {
                // 不选择当前的和选择当前位置的值的数据的最大值
                dp[i][j] = dp[i - 1][j];
                if(j >= v[i]) {
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[n][V]);

        for(int i = 0;i <= n;i++) {
            Arrays.fill(dp[i],0);
        }
        for(int j = 1;j <= V;j++) {
            dp[0][j] = -1;
        }
        // 第二问
        for(int i = 1;i <= n;i++) {
            for(int j = 0;j <= V;j++) {
                // 不选择当前的和选择当前位置的值的数据的最大值
                // 但是是存在条件的，当 dp[i][j] == -1 的时候，说明这个位置的体积数不等于j的，是不合法的
                dp[i][j] = dp[i - 1][j]; //这里直接进行赋值时是因为，当dp[i - 1][j]为-1时候，那么dp[i][j]一定为-1
                if(j >= v[i] && dp[i - 1][j - v[i]] != -1) {
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);
    }
}
